package leetcode.code2013;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

//执行用时：74 ms, 在所有 Java 提交中击败了53.70%的用户
//
//内存消耗：55.3 MB, 在所有 Java 提交中击败了5.56%的用户
//
//通过测试用例：54 / 54

//执行用时：44 ms, 在所有 Java 提交中击败了92.59%的用户
//
//内存消耗：51.8 MB, 在所有 Java 提交中击败了5.56%的用户
//
//通过测试用例：54 / 54
public class DetectSquares {

	int[][] dots;
	Map<Integer, Set<Integer>> row;// <y,set<x>>

	public DetectSquares() {
		dots = new int[1001][1001];
		row = new HashMap<>();
	}

	public void add(int[] point) {
		dots[point[0]][point[1]]++;
		Set<Integer> tmp = row.getOrDefault(point[1], new HashSet<>());
		tmp.add(point[0]);
		row.put(point[1], tmp);
	}

	public int count(int[] point) {
		int x = point[0], y = point[1];
		if (!row.containsKey(y)) {
			return 0;
		}
		Set<Integer> xs = row.get(y);
		int num, num1, num2, yy;
		int ans = 0;
		for (int i : xs) {
			if (i == x)
				continue;
			yy = y - x + i;// 右下
			if (yy <= 1000 && yy >= 0 && (num = dots[i][y]) != 0 && (num1 = dots[x][yy]) != 0
					&& (num2 = dots[i][yy]) != 0) {
				ans += num * num1 * num2;// num * 查询点上不算。
			}
			yy = y + x - i;// 右上
			if (yy <= 1000 && yy >= 0 && (num = dots[i][y]) != 0 && (num1 = dots[x][yy]) != 0
					&& (num2 = dots[i][yy]) != 0) {
				ans += num * num1 * num2;// num * 查询点上不算。
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		DetectSquares detectSquares = new DetectSquares();
		detectSquares.add(new int[] { 3, 10 });
		detectSquares.add(new int[] { 11, 2 });
		detectSquares.add(new int[] { 3, 2 });
		int ans = 0;
		ans = detectSquares.count(new int[] { 11, 10 }); // 返回 1 。你可以选择：
		// - 第一个，第二个，和第三个点
		System.out.println(ans);
		ans = detectSquares.count(new int[] { 14, 8 }); // 返回 0 。查询点无法与数据结构中的这些点构成正方形。
		System.out.println(ans);
		detectSquares.add(new int[] { 11, 2 }); // 允许添加重复的点。
		ans = detectSquares.count(new int[] { 11, 10 }); // 返回 2 。你可以选择：
		System.out.println(ans);
		detectSquares.add(new int[] { 3, 2 }); // 允许添加重复的点。
		ans = detectSquares.count(new int[] { 11, 10 }); // 返回 2 。你可以选择：
		System.out.println(ans);

		// - 第一个，第二个，和第三个点
		// - 第一个，第三个，和第四个点

	}

}
